package heap;

/**
 * Laboratorio de Estrutura de Dados
 * @author talitalm - 20921059
 */


public class HeapImpl implements Heap {
	
	HeapElement[] heapElement;
	int next;
	
	
	private static final int TAM_INICIAL = 20;
	private static final int FATOR = 10;
	
	
	/**
	 * 
	 */
	public HeapImpl() {
		heapElement = new HeapElement[TAM_INICIAL];
		next = 0;
	}

	/**
	 * Metodo auxiliar para retornar o indice que representa o pai do elemento indexado pela posicao i no vetor
	 */
	private int pai(int i) {
		if (i%2 == 0) {
			return (i/2) - 1;
		}
	   return i/2;
	}
	
	/**
	 * Metodo auxiliar para retornar o indice que representa o filho a esquerda do elemento indexado pela posicao i no vetor
	 */
	private int esquerda(int i) {
		return  (2*i) + 1;
	}

	/**
	 * Metodo auxiliar para retornar o indice que representa o filho a direita do elemento indexado pela posicao i no vetor
	 */
	private int direita(int i) {
		return esquerda(i) + 1;
	}
	
	/**
	 * Constroi uma heap a partir de um vetor de dados qualquer. Vamos admitir que
	 * o algoritmo trabalha in-place e que o vetor representando a heap é um atributo da classe
	 */
	private void buildHeap() {
		
		 for ( int posicao = (next - 1)/2 ; posicao >= 0; posicao -- ){
             heapify(posicao);
		 }
	}
	
	/**
	 * Valida o invariante de uma heap a partir de determinada posicao, que pode ser
	 * a raiz da heap ou de uma sub-heap.
	 */
	private void heapify(int posicao) {
		int esquerda = esquerda(posicao);
		int direita = direita(posicao);
		int maximo = posicao;
		
		if ((esquerda < next) && (heapElement[esquerda].compareTo(heapElement[posicao]) == 1)) {
			maximo = esquerda;
		}
		else {
			maximo = posicao;
		}
		if ((direita < next) && heapElement[direita].compareTo(heapElement[maximo]) == 1) {
			maximo = direita;
		}
		
			if (maximo != posicao) {
				swap(posicao, maximo);
				heapify(maximo);
			}
	}
	
	/**
	 * Metodo que troca os elementos nas posicoes i e j de um vetor.
	 * @param i
	 * @param j
	 */
	private void swap(int i, int j) {
		HeapElement temp = heapElement[i];
		heapElement[i] = heapElement[j];
		heapElement[j] = temp;
	}
	
	@Override
	public boolean isEmpty(){
		return next == 0;
	}
	
	@Override
	/**
	 * Insere um elemento na heap e valida o invariante.
	 */
	public void insert(HeapElement object) {

		if (next >= heapElement.length) {
			int tamanhoNovaHeap = heapElement.length + FATOR;
			
			HeapElement[] novoHeap = new HeapElement[tamanhoNovaHeap];
			
			for (int i = 0; i < heapElement.length; i++){
				novoHeap[i] = heapElement[i];
			}
			
			heapElement =  novoHeap;
		}
		
		if (!isEmpty()){
			int i = next;
			
			while (i > 0 && (heapElement[pai(i)].compareTo(object) < 0)) {
				heapElement[i] = heapElement[pai(i)];
				i = pai(i);
			}
			heapElement[i] = object;
			next ++;
		} 
		else {
			heapElement[next] = object;
			next ++;
		}
	}
	
	@Override
	/**
	 *  Remove o elemento com maior chave da heap, retornando-o em seguida.
	 */
	public HeapElement extractMaximum() {
		HeapElement element = null;
		
		if (!isEmpty()) {
			element = heapElement[0];
			swap(0, next);
			next --;
			
			if (next != 0) {
				heapify(0);
			}
		}
		
		return element;
	}

	@Override
	/**
	 * Retorna o elemento com maior chave na heap mas nao remove o mesmo da heap.
	 */
	public HeapElement maximum() {
		return heapElement[0];
	}

	@Override
	/**
	 * Ordena (in-place) a heap e em seguida retorna o próprio vetor interno da heap.
	 */
	public HeapElement[] heapsort() {
		buildHeap();
		for (int i = next - 1 ; next >= 1; --i) {
			swap(0, i);
			next --;
			heapify(0);
		}
		return heapElement;
	}

}